1. Field of the Invention
The present invention relates to computer communication and networking, and more particularly to the layering of packet labels in label switched (virtual path) networks to reduce the size of switching tables.
2. Brief Description of the Prior Art
A problem in connection-oriented networks, in which the connections are provided in the form of virtual circuits or paths, is the build up of “connection state” information, including path table entries, within the switches of the network. In contrast, routing in the Internet, using Internet Protocol (IP) addresses, is “stateless” as it uses bits of the destination IP address carried in each packet to look up the next hop in a route table, thus hierarchically interpreting the address. However, virtual paths, also called label-switched paths, have an inherent advantage over IP routing in that the paths are not bounded, in length or number, by the size of the path index or label space. This advantage is generally unavailable because a global address space was needed for defining the connection in the first place and limited the number of destinations anyway. Another advantage, particularly exploited in asynchronous mode transfer (ATM), is that it is much easier to guarantee quality of service (QoS) using virtual paths (VPs).
Methods for efficient setup for virtual circuits (VCs) with a guaranteed worst case bound and without dependence on a global network address space like IP, is described in copending U.S. Pat. No. 6,802,068, entitled “Addressless Internetworking”, filed July 1999, herein incorporated by reference in its entirety. The method exploits a hierarchical name service resembling the Domain Name Service (DNS), but are constructed in a way that makes it simultaneously a spanning tree and allows control routing by interpreting names as addresses. It is expected that existing routing protocols, including those presently used in the Internet, can be adapted to exploit the name service for obtaining unique switch (router) identifiers for use in computing optimal routes. The switch state volume is then an important remaining problem to be solved for scalability to the Internet scale.
The magnitude of the switch state problem can be estimated as follows. The size of the path table in a typical switch in a connection-oriented network would be M, where M is the mean number of connections passing through that switch, which may be thought of as the density of connections. M would be limited to approximately 10,000, for efficiency and performance. In IP, the number of routes depends on the total number of nodes N in the network, rather than a similar notion of node density, but unlike virtual path indices, IP addresses are interpreted in the course of routing. For example, had the IP (version 4) address space been perfectly aggregated, the entire IP route table would have been simply a distributed binary tree, and the routing decision could have been reduced to 1 bit per router, for a table size of 2 entries and total depth of 32 levels. In reality, IP address assignments have been far from perfect: the initial partitioning of the address space in terms of classes ensured a route table size of at least 256 entries, corresponding to (2log N)1/4=N1/4, and the tables have been further enlarged by Classless Inter-Domain Routing (CIDR), as noted in the Internet Engineering Task Force (IETF) Request for Comments document RFC2775. There is however, a need for a comparable reduction of switch state volume before connection-oriented networking can become usable on the Internet scale.
One proposed method for dealing with switch state volume is the Multi-Protocol Label Switched (MPLS) architecture, providing for the recursive aggregation of aggregate virtual paths, allowing path labels to be nested in the form of a “label stack”. Although the feature appears to be motivated more for switching speed and QoS management, it permits an exponential number of connections to be accommodated at each switch and would reduce the switch state volume to log M. The result would be superior to unaggregated IP in scalability, assuming log M<N1/d, since the size of the Internet, N, will be greater than the capacity of any one switch, M.
The recursive aggregation is also advantageous from another perspective: the aggregate paths, or tunnels, become progressively less representative of actual connections as the level of aggregation increases, and may be considered to represent the state of usage of the network, just as the IP route table is representative of the network topology. Higher level aggregates are likely to be remain useful longer than the individual connections. However, MPLS does not provide a way to guarantee the state reduction on a global scale, as the path labels serve as addresses within MPLS clouds and extending the label space to cover the Internet would reinvent the IP addresses. On the other hand, the labels can be kept local to the individual switches as long as a global address space exists for defining the connections, as provided in ATM. The label stack would then need to be applied on unlimited scale, and it is desirable to perform the aggregation without involving the address space.
Another advantage of aggregation is that it also reduces the signaling latency, because whenever a path is to be created (or destroyed) within an existing tunnel, a setup (teardown) signal does not need to be processed at the intermediate switches traversed by the tunnel. This would eliminate signaling traffic to the intermediate switches whenever broadside-on signaling is used.
Yet another advantage is that with recursive aggregation, connection-oriented networking can provide an indefinitely scalable long term architecture for the Internet as follows. The present IP routing scheme, despite its N1/d scalability of routing, suffers from the inherent bound imposed by its finite address space. There is no way to avoid this limitation other than to widen the packet headers periodically, which is quite difficult as shown by the ongoing IPv6 migration effort, or to make the packet header format independent of the network size, which implies use of relative addressing in some form. Dynamic relative addressing using maps was proposed in the Nimrod scheme (RFC1992) and a more static relative addressing scheme using network address translations (NAT) is proposed in a paper entitled “IPNL: A NAT-Extended Internet Architecture” at SIGCOMM'01. Virtual paths achieve relative addressing on a finer per-switch level of granularity than these methods, and connection-oriented networking is thus a candidate for future long term Internet architecture.
Therefore, a need exists for making connection-oriented networking scalable to the Internet scale and beyond, which can be satisfied only with a means for automatic recursive aggregation of virtual paths.